/*
 * @lc app=leetcode.cn id=234 lang=golang
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
	n := 0
	pre := head
	t := head
	for t != nil {
		t = t.Next
		n++
	}
	node := &ListNode{}
	node.Next = head
	for n > 1 {
		node = node.Next
		n = n - 2
	}
	var post *ListNode
	if n == 1 {
		post = node.Next.Next
	} else {
		post = node.Next
	}
	node.Next = nil

	postRe := reverse(post)

	for pre != nil && postRe != nil {
		if pre.Val != postRe.Val {
			return false
		}
		pre = pre.Next
		postRe = postRe.Next
	}
	return true
}

func reverse(post *ListNode) *ListNode {
	node := &ListNode{}
	for post != nil {
		temp := post
		post = post.Next
		temp.Next = node.Next
		node.Next = temp
	}
	return node.Next
}

// @lc code=end

